/*
Number of Islands Total Accepted: 12280 Total Submissions: 55566 My Submissions Question Solution
Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

11110
11010
11000
00000
Answer: 1

Example 2:

11000
11000
00100
00011
Answer: 3

Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.
*/

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <fstream>
#include <sstream>
#include <unordered_set>
#include <unordered_map>
#include "print.h"
using namespace std;

/**
* Definition for binary tree*/


void testForStack()
{
	stack<int> mystack;
	mystack.push(10);
	mystack.push(20);
	mystack.top() -= 5;
	cout << "mystack.top() is now " << mystack.top() << endl;
}

void testForIntToString()
{
	int a = 10;
	stringstream ss;
	ss << a;
	string str = ss.str();
	cout << str << endl;

	string str1 = to_string(a);

}


/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
	bool dfs(int i, int j, vector<vector<char>> &grid)
	{
		if (i>=0&&i<grid.size()&&j>=0&&j<grid[i].size()&&grid[i][j]=='1')
		{
			grid[i][j] = '2';
			dfs(i - 1,j, grid);
			dfs(i + 1,j, grid);
			dfs(i, j - 1, grid);
			dfs(i, j + 1, grid);
			return true;
		}
		return false;
	}

	int numIslands(vector<vector<char>>& grid) {
		if (grid.size()==0)
		{
			return 0;
		}
		if (grid[0].size()==0)
		{
			return 0;
		}
		int num = 0;
		for (int  i = 0; i < grid.size(); i++)
		{
			for (int j = 0; j < grid[i].size(); j++)
			{
				if (dfs(i, j, grid))
					num++;
			}

		}
		return num;

	}
};
/**
* Your BSTIterator will be called like this:
* BSTIterator i = BSTIterator(root);
* while (i.hasNext()) cout << i.next();
*/

int main(int argc, char* argv[])
{

	vector<char> level1({ '1', '1', '1', '1', '0' });
	vector<char> level2({ '1', '1', '0', '1', '0' });
	vector<char> level3({ '1', '1', '0', '0', '0' });
	vector<char> level4({ '0', '0', '0', '0', '0' });


	vector<vector<char>> grid;
	grid.push_back(level1);
	grid.push_back(level2);
	grid.push_back(level3);
	grid.push_back(level4);


	Solution s;

	int result;
	result = s.numIslands(grid);

	//strRes = s.findRepeatedDnaSequences(s1);
	//cout << "The result is : " << result << endl;
	//result = s.partition(str);
	//stackTree.push(p->left);
	//stackTree.push(p->right);
	//if (s.isPalindrome(str1))
	//	cout << " True" << endl;
	//else
	//	cout << "false" << endl;
	system("pause");
	return 0;
}
//std::unordered_set<std::string> myset =
//{ "hot", "dot", "dog", "lot", "log" };

//std::cout << "myset contains:";
// for (auto it = myset.begin(); it != myset.end(); ++it)
//std::cout << " " << *it;
//;; std::cout << std::endl;

//TreeNode *root = new TreeNode(1);
//TreeNode *left = new TreeNode(2);
//TreeNode *right = new TreeNode(3);

//root->left = left;
//root->right = right;s
/*
//string s1 = "GAGAGAGAGAGA";
string s1 = "GAGAGAGAGAGA";
vector<string> strRes;

TreeNode *root = new TreeNode(1);
TreeNode *left1 = new TreeNode(2);
TreeNode *left2 = new TreeNode(5);

TreeNode *right1 = new TreeNode(3);
TreeNode *right2 = new TreeNode(4);

root->left = left1;
left1->right = left2;

root->right = right1;
right1->right = right2;
*/